package main

import "fmt"

func numIslands(grid [][]byte) int {
	var visited [][]bool
	for i := range grid {
		visited = append(visited, make([]bool, len(grid[i])))
	}
	var cnt int
	if len(grid) == 0 {
		return cnt
	}
	for i := range grid {
		for startIdx := 0; startIdx < len(grid[i]); startIdx++ {
			if visited[i][startIdx] {
				continue
			}
			if grid[i][startIdx] == '1' {
				// BFS
				// c := bfs(grid, i, startIdx, visited)
				// cnt += c

				// DFS
				var c int
				dfs(grid, i, startIdx, visited, &c)
				cnt += c
			}
		}
	}
	return cnt
}

func bfs(grid [][]byte, rowIdx int, startIdx int, visited [][]bool) (c int) {
	// fmt.Println("rowIdx:", rowIdx, startIdx)
	var queue [][]int
	queue = append(queue, []int{rowIdx, startIdx})
	c++
	visited[rowIdx][startIdx] = true
	for len(queue) != 0 {
		rowSize := len(queue)
		for i := 0; i < rowSize; i++ {
			nodeIdx := queue[0]
			queue = queue[1:]
			// BFS不能在这判断visited是true就直接返回，因为还需要判断他的邻接节点是否还有没被访问的，需要加入队列
			// 如果邻接节点联通而且未访问的加入队列
			// 上
			if nodeIdx[0]-1 >= 0 {
				if grid[nodeIdx[0]-1][nodeIdx[1]] == '1' && !visited[nodeIdx[0]-1][nodeIdx[1]] {
					queue = append(queue, []int{nodeIdx[0] - 1, nodeIdx[1]})
					visited[nodeIdx[0]-1][nodeIdx[1]] = true
				}
			}
			// 右
			if nodeIdx[1]+1 < len(grid[rowIdx]) {
				if grid[nodeIdx[0]][nodeIdx[1]+1] == '1' && !visited[nodeIdx[0]][nodeIdx[1]+1] {
					queue = append(queue, []int{nodeIdx[0], nodeIdx[1] + 1})
					visited[nodeIdx[0]][nodeIdx[1]+1] = true
				}
			}
			// 下
			if nodeIdx[0]+1 < len(grid) {
				if grid[nodeIdx[0]+1][nodeIdx[1]] == '1' && !visited[nodeIdx[0]+1][nodeIdx[1]] {
					queue = append(queue, []int{nodeIdx[0] + 1, nodeIdx[1]})
					visited[nodeIdx[0]+1][nodeIdx[1]] = true
				}
			}
			// 左
			if nodeIdx[1]-1 >= 0 {
				if grid[nodeIdx[0]][nodeIdx[1]-1] == '1' && !visited[nodeIdx[0]][nodeIdx[1]-1] {
					queue = append(queue, []int{nodeIdx[0], nodeIdx[1] - 1})
					visited[nodeIdx[0]][nodeIdx[1]-1] = true
				}
			}
		}
	}
	// fmt.Println(visited)
	return
}

func dfs(grid [][]byte, rowIdx, colStartIdx int, visited [][]bool, c *int) {
	if grid[rowIdx][colStartIdx] != '1' {
		return
	}
	if !(visited[rowIdx][colStartIdx]) {
		(*c)++
		visited[rowIdx][colStartIdx] = true
	}
	for i := colStartIdx; i < len(grid[rowIdx]); i++ {

		// 上
		if rowIdx-1 >= 0 {
			if !visited[rowIdx-1][colStartIdx] {
				visited[rowIdx-1][colStartIdx] = true
				dfs(grid, rowIdx-1, colStartIdx, visited, c)
			}
		}
		// 右
		if colStartIdx+1 < len(grid[rowIdx]) {
			if !visited[rowIdx][colStartIdx+1] {
				visited[rowIdx][colStartIdx+1] = true
				dfs(grid, rowIdx, colStartIdx+1, visited, c)
			}
		}
		// 下
		if rowIdx+1 < len(grid) {
			if !visited[rowIdx+1][colStartIdx] {
				visited[rowIdx+1][colStartIdx] = true
				dfs(grid, rowIdx+1, colStartIdx, visited, c)
			}
		}
		// 左
		if colStartIdx-1 >= 0 {
			if !visited[rowIdx][colStartIdx-1] {
				visited[rowIdx][colStartIdx-1] = true
				dfs(grid, rowIdx, colStartIdx-1, visited, c)
			}
		}
	}
}

func main() {
	grid := [][]byte{
		{'1', '1', '1', '1', '0'},
		{'1', '1', '0', '1', '0'},
		{'1', '1', '0', '0', '0'},
		{'0', '0', '0', '0', '0'},
	}
	fmt.Println(numIslands(grid))
}
